package Simple5;
import java.util.HashSet;
public class TwoSigma {

	public static int minLength;
	public static int longest_chain(String[] w){
		
		HashSet<String> set = new HashSet<String>();
		HashSet<Integer> numSet = new HashSet<Integer>();
		minLength = w[0].length();
		for(String s:w){
			set.add(s);
			numSet.add(s.length());
			if(s.length() < minLength){
				minLength = s.length();
			}
		}
		
		int ret = 0;
		for (String string : w) {
			
			int newCount = helper(string, 0, set, numSet);
			if (newCount > ret) {
				ret = newCount;
			}
		}
		
		return ret;
	}
	
	private static int helper(String str, int curCount, HashSet<String> set, HashSet<Integer> numSet){	
		
		if(!set.contains(str)){
			return curCount;
		}
		
		if(str.length() == minLength){
			return curCount + 1;
		}
		
		if (!numSet.contains(str.length() - 1)) {	
			return curCount;
		}
		
		int count = curCount;
		for (int i = 1; i <= str.length(); i++) {				
			String newStr = str.substring(0,i-1) + str.substring(i,str.length());
			 
			int newCount = helper(newStr, curCount+1, set, numSet);
			if(newCount > count){
				count = newCount;
			}
		}
		
		return count;
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		String[] testStrings = {"a","b","ba","bca","bda","bdca"};
		System.out.println(longest_chain(testStrings));
	}
}
